import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class FastAdaptiveArithmeticCoding {
	public static String code(byte[] x, boolean isDCoding) throws UnsupportedEncodingException {
        Map<Byte, Integer> index = new HashMap<Byte, Integer>();
        List<BigInteger> p = new ArrayList<BigInteger>(257);
        List<BigInteger> q = new ArrayList<BigInteger>(257);
        List<Byte> symbols = new ArrayList<Byte>(256);

        p.add(BigInteger.ONE);
        q.add(BigInteger.ONE);

        BigInteger DIV = BigInteger.ONE;

        int[] tau = new int[256];

        BigInteger F = BigInteger.ZERO;
        BigInteger G = BigInteger.ONE;
        BigInteger localDiv = BigInteger.ONE;

		for (int i = 0; i < x.length; i++) {
            byte curr = x[i];
            
            if (!index.containsKey(curr)) {
                F = F.multiply(localDiv).add(G.multiply(q.get(0)));
                G = G.multiply(p.get(0));
                DIV = DIV.multiply(localDiv);

                int myPosition = 0;
                for (byte s = 0; s < curr; ++s) {
                    if (!index.containsKey(s)) {
                        ++myPosition;
                    }
                }
                int mn = symbols.size();
                BigInteger d = BigInteger.valueOf(256 - mn);
                
                F = F.multiply(d).add(G.multiply(BigInteger.valueOf(myPosition)));
                DIV = DIV.multiply(d);

                p.add(null);
                q.add(null);
                index.put(curr, index.size() + 1);
                symbols.add(curr);
            } else {
                int code = index.get(curr);
                F = F.multiply(localDiv).add(G.multiply(q.get(code)));
                G = G.multiply(p.get(code));
                DIV = DIV.multiply(localDiv);
            }
            
            tau[curr & 255]++;

            int mn = symbols.size();
            int n = i + 1;

            if (isDCoding) {
                p.set(0, BigInteger.valueOf(mn));
                localDiv = BigInteger.valueOf(2 * n);
            } else {
                p.set(0, BigInteger.ONE);
                localDiv = BigInteger.valueOf(n + 1);
            }
            q.set(0, BigInteger.ZERO);

            for (int t = 0; t < mn; ++t) {
                byte b = symbols.get(t);
                if (isDCoding) {
                    p.set(t + 1, BigInteger.valueOf(2 * tau[b & 255] - 1));
                } else {
                    p.set(t + 1, BigInteger.valueOf(tau[b & 255]));
                }
                q.set(t + 1, q.get(t).add(p.get(t)));
            }
            if ((i + 1) % 1000 == 0) {
                System.err.println((i + 1) + "/" + x.length);
            }
		}
        System.err.println("evaluation done");

        Fraction fG = new Fraction(G, DIV);
        System.err.println("fG done");

        Fraction fF = new Fraction(F, DIV);
        System.err.println("fF done");

        Fraction value = fF.add(fG.multiply(new Fraction(1, 2)));
        System.err.println("value done");

		int z = fG.inverse().log2up() + 1;
        System.err.println("log2up done");

        StringBuilder result = new StringBuilder();
		String out = value.nBitsAfterComma(z).toString(2);
		while (result.length() + out.length() < z) {
            result.append("0");
		}
        result.append(out);
        System.err.println("all done");
        return result.toString();
	}
	
	public static void main (String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(new FileInputStream("input-big.txt"), "cp1251"));
        StringBuilder data = new StringBuilder();
        String line;
        while ((line = in.readLine()) != null) {
            data.append(line).append("\n");
        }
        String input = data.toString();
		String output = code(input.getBytes("cp1251"), true);
		System.out.println();
		System.out.println(output);
		System.out.println("Input length: " + input.length() * 8 + " bits");
		System.out.println("Output length: " + output.length() + " bits");
	}
}	
